import java.util.Arrays;
import java.util.Comparator;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-10-27
 * Time: 15:27
 */
public class TestHeap {

    private int[] elem;
    private int usedSize;
    public TestHeap(){
        this.elem = new int[10];
    }
    public void createHeap(int[] arr){
        for (int i = 0; i < arr.length; i++){
            elem[i] = arr[i];
            usedSize++;
        }
        for (int parent = ((usedSize - 1 - 1) / 2); parent >= 0 ; parent--) {
            shiftDown(parent, usedSize);
        }
    }
    private void shiftDown(int parent, int end){
        int child = 2 * parent + 1;
        while (child < end){
            if (child + 1 < end){ //判断是否有右子节点
                child = elem[child] > elem[child + 1] ? child : child + 1;//左右子节点最大
                }
            if (elem[child] > elem[parent]){//是否交换
                int tem = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tem;
                parent = child;
                child = 2 * parent + 1;
            }else break;
        }
    }
    public void show(){
        for (int i = 0; i < usedSize; i++) System.out.print(elem[i] + " ");
        System.out.println();
    }
    //插入
    public void offer(int val){
        if (usedSize == elem.length) elem = Arrays.copyOf(elem, 2 * elem.length);
        elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize - 1);
    }
    private void shiftUp(int child){
        int parent = (child  - 1) / 2;
        while(child > 0){
            if (elem[child] > elem[parent]){
                int tem = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tem;
                child = parent;
                parent = (child  - 1) / 2;
            }else break;
        }
    }
    //删除队头元素
    public int poll(){
        if (usedSize == 0) throw new HeapEmptyException("优先级队列为空");
        int tem = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] = tem;
        usedSize--;
        shiftDown(0, usedSize);
        return tem;
    }
    //获取根节点
    public int peek(){
        if (usedSize == 0) throw new HeapEmptyException("优先级队列为空");
        return elem[0];
    }
    public void heapSort(){
        int end = usedSize - 1;
        while (end > 0){
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0, end);
            end--;
        }
    }
}
